package 热题100.子串.和为K的子数组_560_中等;
/*
    前缀和思想，当区间【i，j】和为k，即s[j] - s[i - 1] = k，意思是只要这个公式成立，就有区间之和为k，将公式变换
    s[i - 1] = s[j] - k，只要这个公式成立，就有区间[i,j]和为k，即遍历区间计算出前缀和s[j]，然后用一个map判断s[j] - k是否
    在之前的前缀和中，如果在，就说明有某个前缀和s[i]使得 s[i] = s[j] - k 即【i + 1, j】区间和为k，同时不管在不在都将前缀和
    添加进mp
* */
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public static void main(String[] args){

        System.out.println();
    }

    public static int subarraySum(int[] nums, int k) {
        int sum = 0, ans = 0;
        Map<Integer, Integer> mp = new HashMap<>();
        mp.put(0, 1);
        for (int i = 0; i < nums.length; i ++){
            sum += nums[i];
            if (mp.containsKey(sum - k)){
                ans += mp.get(sum - k);
            }
            mp.put(sum, mp.getOrDefault(sum, 0) + 1);
        }
        return ans;
    }
}
